1. Field of the Invention
The present invention relates to database construction and maintenance within object-oriented programming paradigms. More specifically, the invention relates to a method and apparatus for building and maintaining an object-oriented database of geospatial data for use with the development and maintenance of topological maps consistent with the Vector Product Format, Raster Product Format, and Text Product Standard developed for use by the U.S. Defense Mapping Agency, now known as the National Imagery and Mapping Agency.
2. Description of the Related Art
The use of maps and geographical characteristics has expanded well beyond the navigator, the cartographer, and the classroom the independent field of topology, which is the study of the characteristics, such as adjacency and contiguity, of geometrical objects that are independent of the underlying coordinate system. The primary purpose for providing topological information in contemporary geographic information systems is to expand spatial analysis capabilities. The National Imagery and Mapping Agency (NIMA) is one of many entities that require timely, relevant, and accurate imagery and geospatial information. NIMA maintains and disseminates databases of geographical data in three main formats: Vector Product Format (VPF), Raster Product Format (RPF), and Text Product Standard (TPS).
While the present invention is directed primarily toward VPF products, a brief introduction to the RPF and TPS formats is presented here because the present invention provides for the first time a system that can incorporate into a single platform geospatial data structured in all three formats.
Raster Product Format (RPF) is defined in MIL-STD-2411, 2411-1, and 2411-2 and was developed to facilitate the interchange of raster data between producers and users of raster data by providing a standard database structure for arrays of pixel values. RPF is a standard data structure for geospatial databases composed of rectangular arrays of pixel values (e.g., digitized maps or images) in compressed or uncompressed form. Data in RPF form is intended to be used by application software on computer-readable interchange media, such as CD-ROM""s, directly without further manipulations or transformation. RPF products include those generated from scanned charts, such as those stored in Compressed Arc Digitized Raster Graphics (CADGR), as well as SPOT imagery, such as Controlled Image Base (CIB). In general, RPF data is organized into frame and subframe files. Each frame file contains data for a specific geographical region, defined by a boundary expressed by four (4) latitude/longitude coordinates for a rectangular geographic area. Each frame file also includes a fixed number of data values decomposed into a matrix of subframes, representing color, value, or intensity of the corresponding point. Each product category that represents a single instantiation of RPF, or a family of instantiations of RPF, is described in a separate product specification.
Text Product Standard (TPS) is a textual format using Standard Group Mark-up Language (SGML). TPS provides digital textual information from NIMA hardcopy publications, such as the AMERICAN PRACTICAL NAVIGATOR and SAILING DIRECTIONS. Its information is basically in SGML format. For example, navigators can use TPS data to augment paper or digital charts with valuable information, including accurate directions.
Vector Product Format (VPF) is a standard U.S. Depart of Defense (DOD) format for vector-based digital map products and is defined by U.S. Military Specification MIL-STD-2407, DOD Interface Standard, Vector Product Format, 1996, which is incorporated herein by reference. NIMA, the primary mapping agency for the DOD, developed this standard and is producing an increasing number of digital products in this format. VPF is a standard relational format, structure, and organization for large geographic databases that is based on a georelational vector data model and is intended for direct access by application software. NIMA produces its vector digital map products in this format and offers VPFView as a software application that allows users to browse, display, and perform spatial queries on NIMA data in VPF. NIMA VPF products contain source data from maps, air photographs, satellite data, etc. Other software developers have developed a variety of applications to use and display NIMA-produced VPF data. For example, Environmental Systems Research Institute, Inc. (ESDI) has developed ArcInfo and ArcView to access this data, perform queries, and generally utilize the data within geographic information systems (GIS).
VPF represents a georelational framework based on a vector data model that is well suited to hold data for large geographic databases. Georelational digital vector data are connected points that represent natural and cultural geographic features. Various levels of spatial relationships can be represented in a vector data base such as the VPF data structure. A VPF database comprises three basic types of information for spatial features: spatial geometric properties (locations), non-spatial properties (attributes), and topological properties (relationships). This data is organized into a hierarchical structure of directories, tables, and indices. The root directory for a finite VPF database contains a number of library subdirectories, each representing a specific geographic region and scale. Within each library subdirectory are one or more coverage subdirectories, each representing a related group of feature classes. Each coverage subdirectory contains tables and indices describing its feature classes by attribute (non-spatial) and primitive (spatial) data. Feature data is further subdivided among tile subdirectories within each feature class. Each tile represents a spatial subregion within the library boundaries.
Referring now to FIG. 1, a typical prior art VPF data structure 100 is shown as a relational database with four hierarchical levels: a database level 10; a library level 12; a coverage level 14; and a feature level 16. Within these levels, VPF data is maintained in various types of relational database tables, which are stored as files. VPF tables are ASCII or binary files within the directories that are structured as one or more xe2x80x9ccolumnsxe2x80x9d, or fields for different kinds of information, and many xe2x80x9crowsxe2x80x9d of records for each information type. Such tables are used to feature, attribute, location, geometry, and topology information within the VPF structure. Indices are a special kind of table which have pointers to other tables and records.
At the top level of the VPF structure 100 is the database level 10, a logical collection of data managed as a unit. Each database will contain one or more libraries 11, which are generally organized along a geographic categorization, such as political units or latitude/longitude rectangles. An example of a library is the North American continent. Within each library, the data is organized into coverages 13, which represent features that are thematically and topologically related to each other. Boundaries, rivers, and transportation could all be examples of coverages Coverages are broken down into feature classes 15, each of which represents a homogeneous set of attributes. Transportation features could be roads, railroads, and airports. Feature classes 15 represent areas, lines, points, and/or text and consist of primitive data 17 and attribute data 18. Primitive data 17 describes the location, geometry, and topology of the features with coordinates, or topologically linked sets of nodes, edges, and faces. Attributes 18 are non-spatial data, modeling the thematic information about the features. Because both primitive 17 and attribute 18 information reside in the VPF data structure 100, both spatial (where) relationships and thematic (what) relationships can be modeled with VPF data. Spatial relationships, or topology, include adjacency, connectivity, intersection, containment, and composition.
FIG. 2 displays a block diagram of the hierarchical directory/file structure of the VPF data structure. A typical VPF product has a VPF database directory 20 containing pointers to each of the VPF libraries within each VPF database. Each library has a predefined geographic extent and source scale. Each library directory 22 has coverage subdirectories 24 where linked feature tables 26 store detailed information about thematically similar geospatial features (e.g., transportation, vegetation) and their attributes over the geographic extent of the library. Each feature table 26 includes primitives tables 28 and attributes tables 29. The information retained in these last two structures provide the physical representations of the geographical structures within each coverage level. The primitive tables 28 provide the location, geometry, and topology information of for each coverage level, using winged-edge topology in terms of areas, lines, points, and text. The attributes tables 29 provide physical characteristic information regarding each geographical structure within the coverage level. To facilitate faster access to primitive data, most VPF primitive tables 28 are tiled. Tiles are physical, as opposed to thematic, partitions of data of equal size utilized to break apart large blocks of data into manageable segments. Primitive tables 28 are stored in tile directories 27 within a VPF coverage. Under this structure, topology among VPF features is maintained only within each coverage.
The VPF software offered by NIMA is limited to simple map viewing. VPFView reads a VPF product database, produces user-defined views, and displays those views to the user. The user-built views can be saved to disk and subsequently reloaded for later viewing. While VPFView can be used to query the VPF database, it is limited to simple inquiries because VPFView was never designed to perform sophisticated GIS functions. Further, access to VPF data through non-NIMA software, such as ESDI""s ArcView, often requires prior translation of the VPF database, a process both time-consuming and subsequently restrictive to whatever version of the VPF database existed at the time of translation. Additionally, use of the VPF to dynamically analyze topological information is not possible with any VPF-compatible system presently available. For example, within VPF, a bridge has an existence attribute; i.e., the bridge exists. If the user desires to view and analyze geospatial information in the absence of the bridge, the underlying relational VPF database must first be modified to change the existence attribute for this particular featurexe2x80x94a complex and time-consuming process that requires the updating of all related tables and files.
The VPF structure is known as a, xe2x80x9crelationalxe2x80x9d structure, because pointers and links join, or relate, the various primitives tables 28 and attributes tables 29 within each coverage level. Without this xe2x80x9crelationalxe2x80x9d structure, the data would contain nothing more than simple geometry of the coverage features and not also their topology. This relationship makes VPF products attractive to users of geographic information systems, where spatial analysis is important.
VPF data is stored according to the structure defined in MIL-STD-2407. The Standard specifies the structure for directories, tables, table columns, table join relationships, and media exchange conventions for all VPF data. The data structure itself can be thought of as a template or skeleton within which the geospatial features and metadata are stored. While this standard describes the structure, it does not describe the contents of a set of VPF data; this is the role of a VPF product specification. A product specification corresponding to a specific database product stipulates the precise contents of feature tables and their relationships in the database. In this context, each separate product is defined by a product specification implemented with a VPF structure. Just as different types and scales of maps may be created for a geographic area, each designed for a different use, there are several types of VPF products with differing levels of feature content and density. Each official VPF product is defined by a different military specification describing the particular VPF structure to be utilized. Specification information includes which features, attributes, and attribute values will be allowed in the product as well as how the features will be grouped into coverages and what tiling scheme, if any, will be used. Currently, there are several VPF products being produced by NIMA.
In geographic applications, topology refers to any geographic relationship between connected geometric primitives that is not altered by continuous transformation. VPF recognizes four levels of topology:
Level 0xe2x80x94boundary representation, containing no explicit topological information, for manipulating purely geometric aspects of the spatial data;
Level 1xe2x80x94non-planar graph, suitable for representing networks;
Level 2xe2x80x94planar graph, in which no edges overlap; and
Level 3xe2x80x94full topology, in which no faces overlap.
Level 3 is the most complex topological structure to manage in VPF databases, and winged-edge topology is the format that has been selected for representing level 3 coverages within the VPF database. The function of winged-edge topology is to provide line network and face topology. Three components are necessary to define winged-edge topology: node information, edge information, and face information. An edge knows its neighboring edges by its right edge and left edge attributes. An edge, together with its left and right edges, gives a xe2x80x98wingedxe2x80x99 appearance, leading to the term xe2x80x9cwinged-edgexe2x80x9d topology. Referring now to FIG. 3, an edge 30 has a start node 31, which is connected to the left edge 32, and an end node 33, which is connected to the right edge 34. A neighboring edge 35 is any edge that shares a start node 31 or end node 33 with the original edge 30. Nodes provide contiguity information; for example, each edge 30 knows its start node 31 and end node 33. Start and end nodes also provide orientation information for edges, and define the common point for contiguous edges.
Adjacency information is also maintained by edges. An edge 30 knows its neighboring edges 35 by its right edge 34 and left edge 32 attributes. An edge 30, together with its left 32 and right 34 edges, gives a xe2x80x98wingedxe2x80x99 appearance, leading to the term winged-edge topology. The right edge 34 is the first edge connected to the end node 33 in a counterclockwise direction. The left edge 32 is the first edge connected to the start node 31 in a counterclockwise direction. If there is no neighboring edge 35, the right 34 or the left 32 edge will exist by itself. Each edge also knows its left and right faces, 35 and 36, respectfully. Left 35 and right 36 faces are determined by the edge direction. With these definitions, winged-edge topology provides adjacency, contiguity, and the orientation of neighboring nodes, edges, and faces.
Due to the above rules for level 3 topology, any single line feature may consist of multiple edges; and any single node, edge, or face primitive could be used by more than one feature. Therefore, great care must be taken to maintain the correct linkages between the features and primitives. These complexities place a heavy burden on the maintenance of topological relationships following changes in feature data, especially in a relational database such as the VPF database. With a complex relational database model such as the vector product format, the coverage, features, and topological data resides in many tables that must be queried for every request for information from the database. Furthermore, because of the number of tables involved, maintaining referential integrity of the VPF database upon an update is very difficult. This difficulty arises because the VPF format relies on data residing within multiple specialized tables on multiple levels of the VPF relational database.
Although applications exist to view geospatial data in any of the VPF, RPF, and TPS data formats, no single software product exists to view, query, or manipulate all three formats on a one platform. Therefore, users must access separate programs to utilize data in each format. Cross-referencing data produced in different formats is difficult at best, thereby limiting the speed of assimilating the data and limiting the ability to query and display data from a variety of sources.,
The present inventors have recognized that an object-oriented paradigm provides certain benefits for geographical databases. With an object-oriented data structure, topological and other spatial relationships reside in linked objects, and updates to the data can be handled more simply and directly. This is due to the object-oriented properties of identity, encapsulation, inheritance, and polymorphism. The preferred embodiments of the present invention overcome the problems associated with existing mechanisms for querying, updating, and translating VPF data by providing a geospatial information distribution system that permits easy and complete updating of VPF data, more complex queries of VPF data, and direct exporting of VPF data into a relational database structure. The present invention also permits easy use of data of differing formats and structures within an integrated geospatial information system. In particular, the invention incorporates existing data in VPF, RPF, and TPS files onto a single, object-oriented platform for GIS inquiry.
A primary object of the present invention is to provide a geospatial query and update mapping system that permits easy exporting of data from an object-oriented geospatial database to a relational VPF database.
Another object of the present invention is to provide a geospatial information distribution system that permits easy and complete updating of vector product format data.
A further object of the present invention is to provide a geospatial information distribution system that allows a user to rapidly build a user-specified topological display from a database having vector, raster, and/or text data.
Objects and advantages of the present invention are achieved in accordance with embodiments of the present invention, such as a method of building and maintaining an object-oriented database from a vector product format (VPF) database, including instantiating objects of the object-oriented database, using the VPF database; initializing spatial and non-spatial feature data of the object-oriented database; spatially indexing data among objects across hierarchical levels of the object-oriented database; updating data of the object-oriented database; and exporting the contents of the updated object-oriented database to the VPF database.
Objects and advantages of the present invention are further achieved in accordance with embodiments of the present invention, such as a method of building and maintaining an object-oriented spatial database from at least two of a vector product format (VPF) database, a raster product format (RPF) database, and/or a text product standard (TPS) database, including instantiating objects of the object-oriented database, using at least two of the VPF, RPF, and TPS databases; initializing spatial and non-spatial feature data of the object-oriented database; and spatially indexing data among objects from the at least two VPF, RPF, and TPS databases into the single, object-oriented spatial database.
Objects and advantages of the present invention are further achieved in accordance with embodiments of the present invention, such as a method of building and maintaining an object-oriented database from a VPF database, including instantiating objects of the object-oriented database, using the VPF database; initializing spatial and non-spatial feature data of the object-oriented database; spatially indexing data among objects across hierarchical levels of the object-oriented database; and updating spatial and non-spatial data.
The step of initializing spatial and non-spatial feature data preferably creates a feature level of non-spatial attribute data, which provides characteristic properties of each feature, and spatial data, including primitive data and topological information, which provides spatial relationships between the feature and other features within a specified coverage, and wherein related non-spatial and spatial data are directly accessible from the feature object. Updating spatial and non-spatial data includes adding, changing, and deleting feature, primitive, and topological data within the database and further includes updating all object links referencing the feature, primitive, and topological data. The step of spatially indexing data is applied to one or more flat file, raster product format, vector product format, or text format databases. Data objects can be retrieved from the object-oriented database through user-specified queries, in which the object-oriented database is searched by feature attributes, geometrical constraints, topological constraints, and/or geographical constraints. The retrieved data objects from the query can include flat files, raster images, VPF features, and textual data.
Objects and advantages of the present invention are achieved in accordance with embodiments of the present invention, such as a method of creating an object-oriented database from a relational geospatial database with feature objects having non-spatial data, which provides characteristic properties of each feature, and spatial data, including primitive data and topological information, which provide spatial relationships between a feature object and other feature objects within a specified coverage, wherein related non-spatial and spatial data are directly accessible from the feature object.
Objects and advantages of the present invention are achieved in accordance with embodiments of the present invention, such as a method of searching an object-oriented hierarchical database of spatial data, including listing all databases containing feature data of a user-selected spatial point of interest; listing all libraries, within a user-selected database from the list of databases, containing data intersecting the user-selected spatial point of interest; listing coverages and features, within a user-specified library from the list of libraries; and listing objects from the user-selected database that satisfy a user-selected point of interest and user-selected coverages and/or features, wherein the listed objects include flat files, raster images, VPF features, and textual data.
The database is searchable by one or more of the following data characteristics: feature attributes, geometrical constraints, topological constraints, and geographical constraints.
Objects and advantages of the present invention are achieved in accordance with embodiments of the present invention, such as a computer readable medium encoded with software to build and maintain an object-oriented, hierarchical database from a vector product format (VPF) database.
Objects and advantages of the present invention are achieved in accordance with embodiments of the present invention, such as a computer including a storage medium storing an object-oriented, hierarchical database based on a VPF database; a processor spatially indexing data among objects across hierarchical levels of the object-oriented hierarchical database; a processor searching the object-oriented hierarchical database in response to a user-specified query; and a graphical user interface for accepting the user-specified query and for displaying the results of the object-oriented database search.
Objects and advantages of the present invention are achieved in accordance with embodiments of the present invention, such as a computer program embodied on a computer-readable medium to access an object-oriented spatial database, including a construction code section to build a hierarchy of spatial data, including the levels of library, coverage, and feature data; an addition code section to add data associated with one or more of the hierarchical levels; an indexing code section to spatially index data among objects across hierarchical levels of the object-oriented database; a change code section to update data associated with one or more of the hierarchical levels; and a query code section to search the object-oriented database for user-specified features and to view the search results.
Objects and advantages of the present invention are achieved in accordance with embodiments of the present invention, such as a four-dimensional data structure embodied on a computer-readable medium for building and maintaining an object-oriented spatial database, with the four-dimensional data structure being structured according to database, library, object, and primitive levels; the data at each level being spatially indexed to the data above and below each said level; and the data within the object-oriented spatial database being exported to a relational database in vector product format (VPF).
Objects and advantages of the present invention are achieved in accordance with embodiments of the present invention, such as an apparatus for building and maintaining an object-oriented hierarchical database of spatial data, including a processor spatially indexing objects across hierarchical levels of the object-oriented database such that the spatial data is linked to objects located at levels higher and lower than itself; a storage device on a computer-readable medium on which is stored the object-oriented hierarchical database; a processor updating the spatial data such that the data shared among features is retained; and an output device displaying to a user results of a user-specified query of the object-oriented hierarchical database.
Objects and advantages of the present invention are achieved in accordance with embodiments of the present invention, such as an apparatus for building and maintaining an object-oriented hierarchical database of spatial data, including processor means for transforming data into a linked hierarchical structure; storage means for storing spatially-linked hierarchical data on a computer-readable medium; input means for entering update data for the object-oriented hierarchical database; input means for entering database query instructions; processor means for selecting object-oriented database objects and features that satisfy the database query; and output means for displaying the object-oriented database objects and features that satisfy the database query.